package com.zlk.algorithm.algorithm.sort.merge;

import com.zlk.algorithm.util.RandomUtil;
import org.junit.Test;

import java.util.Arrays;

/**
 * @program: algorithm
 * @ClassName BiggerThanRight
 * @description:
 * 在一个数组中，任何一个前面的数a，
 * 和任何一个后面的数b，如果(a,b)是降序的，就称为降序对 给定一个数组arr，求数组的降序对总数量
 * @author: slfang
 * @create: 2024-01-11 14:52
 * @Version 1.0
 **/
public class BiggerThanRight {

    @Test
    public void test(){
        int testTimes = 100000;
        int maxVal=100;
        int maxLength=30;
        for (int i = 0; i < testTimes; i++) {
            int[] randomArr = RandomUtil.generateRandomArray(maxLength, maxVal);
            int[] randomArrCopy = Arrays.copyOf(randomArr, randomArr.length);
            int i1 = biggerThanRight(randomArr);
            int i2 = comparator(randomArrCopy);
            if(i1!=i2){
                System.out.println("smallSum::"+i1); //[-2, 3, 2, -5, 2, -6]
                System.out.println("testSum::"+i2); // 2  4  1 1
                //
                System.out.println(Arrays.toString(randomArrCopy));
                break;
            }
        }
        System.out.println("ok");
    }

    public static int comparator(int[] arr) {
        int ans = 0;
        for (int i = 0; i < arr.length; i++) {
            for (int j = i + 1; j < arr.length; j++) {
                if (arr[i] > arr[j]) {
                    ans++;
                }
            }
        }
        return ans;
    }

    private int testBiggerThanRight(int[] arr) {
        int count = 0;
        if(arr.length<2||arr==null){
            return  count;
        }
        for (int i = 0; i < arr.length; i++) {
            for (int j = i+1; j < arr.length; j++) {
                count+=arr[i]>arr[j]?1:0;
            }
        }
        return count;
    }


    @Test
    public void test2(){
        //4,0,1,2,-5,0
        //0 4  1  2  -5 0
        //    0 1 2 4
        int[] arr = new int[]{4,0,1,2,-5,0};
        System.out.println(biggerThanRight(arr));
    }
    int biggerThanRight(int[] arr){
        int count = 0;
        if(arr.length<2||arr==null){
            return  count;
        }
        return sortCount(arr,0,arr.length-1);
    }

    private int sortCount(int[] arr, int l, int r) {
        if(l==r){
            return 0;
        }
        int mid = l+((r-l)>>1);
        return sortCount(arr,l,mid)+sortCount(arr,mid+1,r)+merage(arr,l,mid,r);

    }


    private int merage(int[] arr, int l, int mid, int r) {
        int lIndex = l;
        int rIndex = mid+1;
        int[] temp = new int[r-l+1];
        int index =0;
        int count = 0;
        while (lIndex<=mid&&rIndex<=r){ //
            count +=arr[lIndex]>arr[rIndex]?(r-rIndex+1):0;
            temp[index++]=arr[lIndex]>arr[rIndex]?arr[lIndex++]:arr[rIndex++];
        }
        while (lIndex<=mid){
            temp[index++] = arr[lIndex++];
        }
        while (rIndex<=r){
            temp[index++] = arr[rIndex++];
        }
        for (int i = 0; i < temp.length; i++) {
            arr[l+i] = temp[i];
        }
        return count;
    }

    //[-5, 8, 2, -4, 9, 2]
    // 8 -5  2  -4   9   2       ：2
    //8  2  -4     9 8 2          ：2
    //9 8 2 2  -4

}
